package psn.zjk.career.interview.algorithm.sort;

import java.util.Arrays;

/**
 * @USER white
 * @DATETIME 2021/1/13 12:16
 */
public class QuickSort2 {

    public int[] sort(int[] nums) {
        int[] ts = Arrays.copyOf(nums, nums.length);
        sort(ts, 0, nums.length - 1);
        return ts;
    }

    private int partition(int[] nums, int left, int right) {
        int base = left;
        int smaller = left + 1;//最右边的已交互小数下标+1，从基数右边第一个开始
        for (int scannIndex = smaller; scannIndex <= right; scannIndex++) {
            if (nums[scannIndex] > nums[base]) {//倒序，大数在前
                swap(nums, scannIndex, smaller);
                smaller++;
            }
        }
        swap(nums, base, smaller - 1);//交互基数与最后一个已交互小数
        return smaller - 1;
    }

    private void swap(int[] nums, int index1, int index2) {
        if (index1 != index2) {
            int tmp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = tmp;
        }
    }

    private void sort(int[] nums, int left, int right) {
        if (left < right) {
            //分区
            int partition = partition(nums, left, right);
            System.out.println(partition);
            //左分区排序
            sort(nums, left, partition - 1);
            //右分区排序
            sort(nums, partition + 1, right);
        }
    }


    public static void main(String[] args) throws Exception {
        int[] numbers = {12, 15, 1, 18, 2, 35, 30, 11, 312};
        Arrays.stream(numbers).forEach(num -> {
            System.out.print(num + " ");
        });
        System.out.println();
        //数组不建议用lambada
        Arrays.stream(new QuickSort2().sort(numbers)).forEach(num -> {
            System.out.print(num + " ");
        });
    }
}
